11244. Sum of two

 

Given an array A, sorted in ascending order and containing n integers. Determine whether there exists a pair of numbers (Ai, Aj), where i < j, such that their sum is equal to x.

 

Input. The first line contains two integers n (n ≤ 105) and x (x ≤ 106). The second line contains n non-negative integers, each of which is not greater than 106.

 

Output. Print “YES” if such a pair of elements exists, and “NO” otherwise.

 

Sample input 1

Sample output 1

10 13

1 3 5 6 8 10 11 11 11 16

YES

 

 

Sample input 2

Sample output 2

8 61

5 5 8 12 16 21 44 50

NO

 

 

SOLUTION

two pointers

 

Algorithm analysis

Let v be the input array of numbers. Initialize pointers i = 0 to the beginning of the array and j = n – 1 to the end of the array. The array is already sorted according to the problem conditions.

While pointers i and j do not meet, perform the following actions:

·        If v[i] + v[j] = x, then the desired pair of elements is found. Print it and terminate the program.

·        If v[i] + v[j] < x, then move pointer i one position to the right. In this case, the sum v[i] + v[j] will increase.

·        If v[i] + v[j] > x, then move pointer j one position to the left. In this case, the sum v[i] + v[j] will decrease.

 

Example

Let’s consider the first test. Initialize the pointers. Simulate the algorithm’s operation. The value of x = 13, we are looking for two numbers with a sum of 13.

 

 

Algorithm realization

Read the input data.

 

scanf("%d %d", &n, &x);

v.resize(n);

for (i = 0; i < n; i++)

  scanf("%d", &v[i]);

 

Initialize the pointers. 

 

int i = 0, j = v.size() - 1;

 

Move pointer i forward and pointer j backward.

 

while (i < j)

{

 

If v[i] + v[j] = x, then the desired pair of elements is found. Print it and terminate the program.

 

  if (v[i] + v[j] == x)

  {

    printf("YES\n");

    return 0;

  }

 

If v[i] + v[j] < x, then move pointer i one position to the right;

If v[i] + v[j] > x, then move pointer j one position to the left;

 

  if (v[i] + v[j] < x) i++; else j--;

}

 

If the desired pair is not found, print “NO”.

 

printf("NO\n");

 

Java realization

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int x = con.nextInt();

    int v[] = new int[n];

    for(int i = 0; i < n; i++)

      v[i] = con.nextInt();

 

    int i = 0, j = n - 1;

    while (i < j)

    {

      if (v[i] + v[j] == x)

      {

        System.out.println("YES");

        return;

      }

      if (v[i] + v[j] < x) i++; else j--;

    }

    System.out.println("NO");

    con.close();

  }

}

 

Python realization

Read the input data.

 

n, x = map(int,input().split())

lst = list(map(int,input().split()))

 

Initialize the pointers. 

 

i = 0

j = n – 1

 

Move pointer i forward and pointer j backward.

 

while (i < j):

 

If v[i] + v[j] = x, then the desired pair of elements is found. Print it and terminate the program.

 

  if (lst[i] + lst[j] == x):

    print("YES")

    exit()

 

If v[i] + v[j] < x, then move pointer i one position to the right;

If v[i] + v[j] > x, then move pointer j one position to the left;

 

  if (lst[i] + lst[j] < x):

    i += 1

  else:

    j -= 1

 

If the desired pair is not found, print “NO”.

 

print("NO")